package com.bishi;

import java.util.Arrays;

/**
 * m*n的网格，从左上角到右下角，距离最短
 */
public class 奇安信 {
    public static void main(String[] args) {
        int[][] arr = {{1,3,16},{10,11,-1},{1,14,14}};
        int ans = minPathSum(arr);
        System.out.println(ans);
    }

    public static int minPathSum (int[][] grid) {
        // write code here
        int m = grid.length;
        int n = grid[0].length;
        if(grid[0][0] == -1 || grid[m-1][n-1] == -1){
            return 0;
        }
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = grid[0][0];
        for(int i = 1; i< n; i++){
            if(grid[0][i] == -1){
                break;
            } else {
                dp[0][i] = dp[0][i-1]+grid[0][i];
            }
        }
        for(int j = 1; j < m; j++){
            if(grid[j][0] == -1){
                break;
            } else {
                dp[j][0] = grid[j][0] +dp[j-1][0];
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1;j < n;j++){
                if(grid[i][j] == -1){
                    break;
                } else {
                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
